package com.gitee.ywj1352.算法.week02;

import java.util.*;

/**
 * 1.给定一个二叉树的根节点 root ，返回它的 中序 遍历。
 */
public class 二叉树遍历 {

    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(5);
        TreeNode t6 = new TreeNode(6);
        TreeNode t7 = new TreeNode(7);
        TreeNode t8 = new TreeNode(8);
        t5.left = t3;
        t5.right = t8;
        t3.left = t2;
        t3.right = t4;
        t2.left = t1;
        t8.left = t6;
        t8.right = t7;


        List<Integer> integers = inorderTraversal4(t5);

        System.out.println(integers);

    }

    /**
     * 中序遍历  递归放肆
     *
     * @param root
     * @return
     */
    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        helperInorder(root, res);
        return res;
    }


    /**
     * 自己想的 太搓了
     *
     * @param root
     * @return
     */
    public static List<Integer> inorderTraversal2(TreeNode root) {
        Stack<Pair> stack = new Stack<>();
        stack.push(new Pair(root, 0));
        List<Integer> res = new ArrayList<>();
        while (!stack.isEmpty()) {
            Pair peek = stack.peek();
            if (peek.treeNode.left != null && peek.code == 0) {
                peek.code = -1;
                stack.push(new Pair(peek.treeNode.left, 0));
                continue;
            }
            if (
                    (peek.treeNode.left == null && peek.treeNode.right == null) ||
                            (peek.code == 1) ||
                            (peek.treeNode.left != null && peek.code == -1) ||
                            (peek.treeNode.left == null && peek.code == 0)
            ) {
                res.add(peek.treeNode.val);
                stack.pop();
                if (peek.treeNode.right != null && peek.code != 1) {
                    stack.push(new Pair(peek.treeNode.right, 0));
                }
                continue;
            }
            if (peek.treeNode.right != null && peek.code != 1) {
                peek.code = 1;
                stack.push(new Pair(peek.treeNode.right, 0));
            }
        }
        return res;
    }

    public static class Pair {
        TreeNode treeNode;
        int code = 0;

        public Pair(TreeNode treeNode, int code) {
            this.code = code;
            this.treeNode = treeNode;

        }
    }


    public static void helperInorder(TreeNode treeNode, List<Integer> nums) {
        if (treeNode == null) return;
        helperInorder(treeNode.left, nums);
        nums.add(treeNode.val);
        helperInorder(treeNode.right, nums);
    }


    //中序遍历
    public static List<Integer> inorderTraversal4(TreeNode root) {
        if (root == null) return null;
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }


    //前序遍历
    public static List<Integer> preTraversal(){



        return null;
    }






    //后序遍历

}
